#pragma once 
#include <iostream>
#include <vector>
using namespace std;

namespace clx 
{
  template<class T> 
  struct Less
  {
    bool operator()(const T& l, const T& r)
    {
      return l < r;
    }
  };
  template<class T>
  struct greater 
  {
    bool operator()(const T& l, const T& r)
    {
      return l > r;
    }
  };
  template<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
  class priority_queue
  {
    public:
      void AdjustUp(size_t child)
      {
        Compare com;
        size_t parent = (child - 1) / 2;
        while (child > 0)
        {
          if (com(_con[parent], _con[child]))
          {
            swap(_con[parent], _con[child]);
            child = parent;
            parent = (child - 1) / 2;
          }
          else 
          {
            break;
          }
        }

      }
      void push(const T& x)
      {
        _con.push_back(x);
        //向上调整
        AdjustUp(_con.size() -1);
      }
      void AdjustDown(size_t parent)
      {
        Compare com;
        size_t child = parent * 2 + 1;
        while (child < _con.size())
        {
          if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
          {
            child += 1;
          }
          if (com(_con[parent], _con[child]))
          {
            swap(_con[parent], _con[child]);
            parent = child;
            child = 2 * parent + 1;
          }
          else 
          {
            break;
          }
        }


      }
      void pop()
      {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        //向下调整
        AdjustDown(0);

      }
      T& top()
      {
        return _con[0];
      }
      bool empty() 
      {
        return _con.empty();
      }
    private:
      Container _con;
  };
  void priority_queue_test();
}

void clx::priority_queue_test()
{
  clx::priority_queue<int, vector<int>, greater<int>> pq;
  pq.push(3);
  pq.push(5);
  pq.push(6);
  pq.push(1);
  pq.push(4);

  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }
  cout << endl;

}


